package com.dzsw.datastruct.tree.binary;

interface IBinaryTree<E> {

    /**
     * 获取元素节点的数量
     * @return
     */
    int size();

    /**
     * 判断树是否为空树
     * @return
     */
    boolean isEmpty();

    /**
     * 清空树的所有元素
     */
    void clear();

    /**
     * # 前序遍历（Preorder Traversal）
     * - 根节点访问在前
     *
     * ## 访问顺序：
     * - 根节点 => 前序遍历左子树 => 前序遍历右子树
     */
    void preOrder(Visitor<E> visitor);

    /**
     * # 中序遍历（Inorder Traversal）
     * - 根节点访问在中
     *
     * ## 访问顺序：
     * - 1. 中序遍历左子树 => 根节点 => 中序遍历右子树（如果是二叉搜索树，结果升序）
     * - 2. 中序遍历右子树 => 根节点 => 中序遍历左子树（如果是二叉搜索树，结果降序）
     * @param visitor
     */
    void inOrder(Visitor<E> visitor);

    /**
     * # 后序遍历（Postorder Traversal）
     * - 根节点访问在后
     *
     * ## 访问顺序
     * - 后序遍历左子树 => 后序遍历右子树 => 根节点
     */
    void postOrder(Visitor<E> visitor);

    /**
     * # 层序遍历（Level Order Traversal）
     *
     * ## 访问顺序：
     * - 从上到下、从左到右依次访问每一个节点
     */
    void levelOrder(Visitor<E> visitor);

    /**
     * 计算树的高度
     */
    int height();

    /**
     * 判断是否为完全二叉树
     */
    boolean isComplete();

    /**
     * 判断是否为真二叉树
     */
    boolean isProper();

    /**
     * 重写 toString 方法，树状打印二叉树
     */
    String toString();

    /**
     * 获取传入节点的前驱节点
     *
     * @param node
     * @return
     */
    Node<E> predecessor(Node<E> node);

    /**
     * 获取传入节点的后继节点
     *
     * @param node
     * @return
     */
    Node<E> successor(Node<E> node);
}
